package linkedList;

/** 单向循环链表解决约瑟夫问题 */
public class CircleSingleLinkedListDemo {

  public static void main(String[] args) {

    CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();

    circleSingleLinkedList.add(125);
    circleSingleLinkedList.list();

    circleSingleLinkedList.josephu(10,20,125);
  }
}

class CircleSingleLinkedList {
  Child first = null;

  // 添加结点
  public void add(int num) {
    if (num < 1) {
      System.out.println("num小于1个");
      return;
    }

    Child cur = null;
    for (int i = 1; i <= num; i++) {
      Child child = new Child(i);
      if (i == 1) {
        first = child;
        first.next = first;
        cur = first;
      }
      cur.next = child;
      child.next = first;
      cur = cur.next;
    }
  }

  // 遍历
  public void list() {
    if (first == null) {
      System.out.println("链表为空");
      return;
    }
    Child cur = first;
    while (true) {
      System.out.println("编号为" + cur.getId());
      if (cur.next == first) {
        break;
      }
      cur = cur.next;
    }
  }

  /**
   * 约瑟夫问题
   * @param start 开始结点
   * @param count 每次移动结点数
   * @param total 结点总数
   */
  public void josephu(int start, int count, int total) {
    if (start < 1 || count > total) {
      System.out.println("参数有误");
      return;
    }
    // 1.让temp指向first的前一个结点
    Child temp = first;
    while (true) {
      if (temp.next == first) {
        break;
      }
      temp=temp.next;
    }
    // 2.temp和first都后移start
    for (int i = 0; i < start - 1; i++) {
      first = first.next;
      temp = temp.next;
    }
    // 3.结点依次出圈
    while (true) {
      if (temp == first) {
        break;
      }
      for (int i = 0; i < count - 1; i++) {
        first = first.next;
        temp = temp.next;
      }
      System.out.printf("第%d个结点出圈\n", first.getId());
      first = first.next;
      temp.next = first;
    }
    System.out.printf("最后一个结点%d出圈\n", first.getId());
  }
}

class Child {

  int id;
  Child next;

  public Child() {}

  public Child(int id) {
    this.id = id;
  }

  public int getId() {
    return id;
  }

  public Child getNext() {
    return next;
  }
}
